/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution
{
public:
    Node *cloneGraph(Node *node)
    {
        if (node == nullptr)
        {
            return nullptr;
        }
        Node *origin = node;
        unordered_map<int, set<int>> adjTable;
        unordered_set<Node *> visited;
        stack<Node *> s;
        s.push(node);
        visited.insert(node);
        while (!s.empty())
        {
            Node *cur = s.top();
            for (Node *adjNode : cur->neighbors)
            {
                adjTable[cur->val].insert(adjNode->val);
                if (!visited.count(adjNode))
                {
                    visited.insert(adjNode);
                    s.push(adjNode);
                }
            }
            if (cur == s.top())
            {
                s.pop();
            }
        }

        int n = adjTable.size();
        if (n == 0)
        {
            return new Node(origin->val);
        }
        vector<Node *> copies(n + 1, nullptr);
        for (auto &[val, adjs] : adjTable)
        {
            if (copies[val] == nullptr)
            {
                copies[val] = new Node(val);
            }
            for (int adjVal : adjs)
            {
                if (copies[adjVal] == nullptr)
                {
                    copies[adjVal] = new Node(adjVal);
                }
                copies[val]->neighbors.push_back(copies[adjVal]);
            }
        }
        return copies[origin->val];
    }
};